数学模型

Wang Haihua

🍈 🍉🍊 🍋 🍌

---

选址问题

概念

选址问题是指在某个区域内选择设施的位置使所需的目标达到最优。选址问题也是一种互斥的计划问题。

例如投资场所的选址：企业要在 $m$ 个候选位置选择若干个建厂，已知建厂费用、运输费及 $n$ 个地区的产品需求量，应如何进行选址。

选址问题是运筹学中经典的问题之一，选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。更重要的，选址问题也是数模竞赛的热点问题。

选址是重要的长期决策，选址的好坏直接影响到服务方式、服务质量、服务效率、服务成本等，从而影响到利润和市场竞争力，选址问题的研究有着重大的经济、社会和军事意义。

要素

选址问题有四个基本要素：设施、区域、距离和优化目标。

设施

选址问题中所说的设施，在具体题目中可以是工厂、仓库、服务站等形式。

区域

选址问题中所说的区域，在具体题目中可以是工厂、车间的内部布局，也可以是给定的某个地区、甚至空间范围。

按照规划区域的特征，可以分为连续选址问题和离散选址问题。连续选址问题，设施可以布局在区域内的任意位置，就要求出最优选址的坐标；离散选址问题，只能从若干候选位置中进行选择，运筹学中的选址问题通常是这类离散选址问题。

距离

选址问题中所说的距离，是指设施到服务对象之间的距离，在具体题目中也可以是某个选址位置的服务时间、成本、覆盖范围。如果用图论方法求解，通常就是连接顶点的边的权值。

当问题所关注的是设施到服务对象之间的距离时，如果问题给出的不是顶点之间的距离，而是设施的位置坐标，要注意不是只有欧式距离，对于不同问题也可能是球面距离、曼哈顿距离、切比雪夫距离。

优化目标

选址问题要求选择最好的选址位置，但选址位置只是决策变量，选择的最终目的通常是实现加权距离最短、费用最小、利润最大、时间最短，这才是优化问题的目标函数。

按照目标函数的特点，可以分为：中位问题，要求总成本最小；中心问题，服务于每个客户的最大成本最小；反中心问题：服务于每个客户的最小成本最大。

案例(消防站的选址问题)

问题

某城市有 8 个区，每个区最多建一个消防站，拟建设消防站到各区的最长时间如下表所示。现要求任何区域发生火警时，消防车能在 15分钟内赶到。在此条件下尽量减少消防站数量，应该在哪几个区建设消防站？

-	1	2	3	4	5	6	7	8
1	7	12	18	20	24	26	25	28
2	14	5	8	15	16	18	18	18
3	19	9	4	14	10	22	16	13
4	14	15	15	10	18	15	14	18
5	20	18	12	20	9	25	14	12
6	18	21	20	16	20	6	10	15
7	22	18	20	15	16	15	5	9
8	30	22	15	20	14	18	8	6

分析

问题要求从 8 个候选消防站中选择若干个，在所有需求点得到服务的时间都小于临界值 15分钟的条件下，选择消防站的数量最少。本问题不考虑各候选站点建设费用的差异，即不带权重。

建模

变量及参数

定义参数$R_{ij}$为每个消防站的覆盖范围：

$$R_{ij} \begin{cases} 1,第i个消防站可覆盖第j个区域 \\ 0,第i个消防站不可覆盖第j个区域 \end{cases} $$

由拟建消防站到各区的最长时间表可以得到参数$R_{ij}$ 如下表：

-	1	2	3	4	5	6	7	8
1	1	0	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	0	1	0	0	0
4	0	0	0	1	0	0	0	0
5	0	0	0	0	1	0	0	0
6	0	0	0	0	0	1	1	0
7	0	0	0	0	0	0	1	1
8	0	0	0	0	0	0	1	1

定义决策变量 $x_j$为选中的服务站

模型

可以建立数学模型如下：

$$ \begin{aligned} &{\min \quad \sum_{i=1}^8 x_j} \\ s.t.&\left\{\begin{array}{ll} {\displaystyle\sum_{j=1}^{8} R_{ij} \ge 1, i=1,2,...,8} \\ {x_{j}=0 或 1,j=1,2,...,8} \end{array}\right. \end{aligned} $$

求解

使用Pulp库进行求解

最终设立消防站的情况如下表所示

	设立消防站
0	0
1	1
2	0
3	0
4	0
5	0
6	1
7	0

---

import numpy as np
import pulp as lp
import pandas as pd
from model_insight.load_datasets import load_firestation

station = load_firestation()

station

	0	1	2	3	4	5	6	7
0	7	12	18	20	24	26	25	28
1	14	5	8	15	16	18	18	18
2	19	9	4	14	10	22	16	13
3	14	15	15	10	18	15	14	18
4	20	18	12	20	9	25	14	12
5	18	21	20	16	20	6	10	15
6	22	18	20	15	16	15	5	9
7	30	22	15	20	14	18	8	6

station[station<=15] = 1 
station[station>15]=0

station

	0	1	2	3	4	5	6	7
0	1	1	0	0	0	0	0	0
1	1	1	1	1	0	0	0	0
2	0	1	1	1	1	0	0	1
3	1	1	1	1	0	1	1	0
4	0	0	1	0	1	0	1	1
5	0	0	0	0	0	1	1	1
6	0	0	0	1	0	1	1	1
7	0	0	1	0	1	0	1	1

# initialize the model and data
model = lp.LpProblem(name="firestation",sense=lp.LpMinimize)

dists = station.index

# variables
xi = lp.LpVariable.dicts(name='whether_set',indexs=dists,cat='Binary')

# objective funtion
objective = lp.lpSum([xi[i] for i in dists])
model += objective,'objective_function'
# constraints
## for each district, at least 1 firestation is available
for i in dists:
    model +=lp.lpSum(xi[j]*station.loc[i,j] for j in dists)>=1,f'constraint_available_{i}'

model.solve()

1

df_result = pd.DataFrame(np.zeros((8,1)),index=dists,columns=['设立消防站'])
for i in dists:
    df_result.loc[i,'设立消防站']=lp.value(xi[i])

df_result

	设立消防站
0	0.0
1	1.0
2	0.0
3	0.0
4	0.0
5	0.0
6	1.0
7	0.0